package done.easy_501_600;

import com.study.common.TreeNode;
import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import static com.study.common.TreeNode.printRight;

/**
 * 897. Increasing Order Search Tree 递增顺序查找树
 * <p>
 * 给定一个树，按中序遍历重新排列树，使树中最左边的结点现
 * 在是树的根，并且每个结点没有左子结点，只有一个右子结点。
 * <p>
 * 示例 ：
 * 输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]
 * <p>
 * 5
 * / \
 * 3    6
 * / \    \
 * 2   4    8
 * /        / \
 * 1        7   9
 * <p>
 * 输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
 * <p>
 * 1
 * \
 * 2
 * \
 * 3
 * \
 * 4
 * \
 * 5
 * \
 * 6
 * \
 * 7
 * \
 * 8
 * \
 * 9
 *
 * @author 大硕
 * 2019-04-05 8:03 PM
 **/
@Slf4j
@SuppressWarnings("all")
public class IncreasingOrderSearchTree {

    public TreeNode increasingBST(TreeNode root) {
        // 190406 first
        return null;
    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(5,
                new TreeNode(3,
                        new TreeNode(2,
                                1), 4), new TreeNode(6,
                null, new TreeNode(8,
                7, 9)));
        TreeNode tn = increasingBST(root);
        log.info("{}", printRight(tn));
    }
}


























/*
// 初始化全局指针
TreeNode ans;

public TreeNode increasingBST(TreeNode root) {
    TreeNode res = new TreeNode(0);

    // 利用一个全局指针遍历
    ans = res;

    // 递归
    dfs(root);

    return res.right;

}

//中序遍历是 ① 左 -> ② 中 -> ③ 右
public void dfs(TreeNode node){
    if(node != null){
        // ① 先左
        dfs(node.left);

        // ② 再中
        ans.right = new TreeNode(node.val);
        ans.left = null;
        ans = ans.right;

        // ③ 后右
        dfs(node.right);
    }
}
*/
